def is_valid(board, row, col, value):
    """检查将value(1 or 0) 放在board[row][col]是否有效"""
    n = len(board)

    # 检查行
    count = 0
    for i in range(n):
        if board[row][i] == value:
            count += 1
        else:
            count = 0
        if count > 2:
            return False

    # 检查列
    count = 0
    for i in range(n):
        if board[i][col] == value:
            count += 1
        else:
            count = 0
        if count > 2:
            return False

    # 检查行和列的黑白棋子数量是否平衡
    row_ones = sum(1 for x in board[row] if x == 1)
    col_ones = sum(1 for x in [board[i][col] for i in range(n)] if x == 1)

    if row_ones > n // 2 or col_ones > n // 2:
        return False

    return True


def is_row_unique(board, row):
    """检查当前行是否与其他行重复"""
    for i in range(len(board)):
        if i != row and board[i] == board[row]:
            return False
    return True


def is_col_unique(board, col):
    """检查当前列是否与其他列重复"""
    n = len(board)
    current_col = [board[i][col] for i in range(n)]

    for j in range(n):
        if j != col:
            other_col = [board[i][j] for i in range(n)]
            if current_col == other_col:
                return False
    return True


def is_solved(board):
    """检查棋盘是否已完全解决"""
    n = len(board)

    # 检查黑白棋子数量
    for i in range(n):
        if sum(1 for x in board[i] if x == 1) != n // 2:
            return False
        if sum(1 for x in [board[j][i] for j in range(n)] if x == 1) != n // 2:
            return False

    # 检查唯一性
    for i in range(n):
        if not is_row_unique(board, i) or not is_col_unique(board, i):
            return False

    # 检查是否有连续三个相同棋子
    for row in range(n):
        for col in range(n - 2):
            if board[row][col] == board[row][col + 1] == board[row][col + 2] != 2:  # 确保已经填入值
                return False

    for col in range(n):
        for row in range(n - 2):
            if board[row][col] == board[row + 1][col] == board[row + 2][col] != 2:  # 确保已经填入值
                return False

    return True


def solve_puzzle(board):
    """使用DFS解决黑白棋填充难题"""
    n = len(board)

    def find_empty_cell():
        for i in range(n):
            for j in range(n):
                if board[i][j] == 2:
                    return i, j
        return None

    def backtrack():
        empty_cell = find_empty_cell()
        if not empty_cell:
            return is_solved(board)  # 如果没有空单元格，检查是否解决

        row, col = empty_cell

        for value in [0, 1]:
            board[row][col] = value
            if is_valid(board, row, col, value):
                if backtrack():
                    return True  # 找到解决方案
            board[row][col] = 2  # 重置为初始状态

        return False  # 没有找到解决方案

    if backtrack():
        return board
    else:
        return None


# 初始棋盘
board = [[1, 0, 1, 0, 2, 2],
         [2, 2, 2, 0, 2, 2],
         [2, 2, 2, 1, 0, 0],
         [2, 2, 2, 2, 2, 2],
         [2, 2, 1, 2, 2, 1],
         [2, 0, 2, 2, 1, 2]]

# 解决难题
solved_board = solve_puzzle(board)

# 输出结果
if solved_board:
    result_string = "".join(str(cell) for row in solved_board for cell in row)
    print(result_string)
else:
    print("No solution found.")
